package com.xyhuo.leetcode.december;

import java.util.ArrayList;
import java.util.List;

/**
 * 重新规划路线
 * https://leetcode.cn/problems/reorder-routes-to-make-all-paths-lead-to-the-city-zero
 *
 * @time 2023/12/7
 */
public class MinReorder {

//    public static void main(String[] args) {
//        MinReorder mr = new MinReorder();
//        int[][] connections = {{0, 1}, {1, 3}, {2, 3}, {4, 0}, {4, 5}};
//        mr.minReorder(6, connections);
//    }

    public int minReorder(int n, int[][] connections) {
        List<Integer>[][] dp = new List[n][2];
        for (int i = 0; i < n; i++) {
            dp[i][0] = new ArrayList<>();
            dp[i][1] = new ArrayList<>();
        }
        for (int i = 0; i < n - 1; i++) {
            dp[connections[i][0]][0].add(connections[i][1]);
            dp[connections[i][1]][1].add(connections[i][0]);
        }
        dfs(0, -1, dp);
        return ans;
    }

    private int ans = 0;

    private void dfs(int index, int parentIndex, List<Integer>[][] dp) {
        for (Integer nextIndex : dp[index][0]) {
            if (nextIndex != parentIndex) {
                ans++;
                dfs(nextIndex, index, dp);
            }
        }
        for (Integer nextIndex : dp[index][1]) {
            if (nextIndex != parentIndex) {
                dfs(nextIndex, index, dp);
            }
        }
    }
}
